/*
 * Project: BoboDesignPattern
 * 
 * File Created at 2019年7月4日
 * 
 * Copyright 2012 Greenline.com Corporation Limited.
 * All rights reserved.
 *
 * This software is the confidential and proprietary information of
 * Greenline Company. ("Confidential Information").  You shall not
 * disclose such Confidential Information and shall use it only in
 * accordance with the terms of the license agreement you entered into
 * with Greenline.com.
 */
package test.lesson3.graph;

import java.util.Stack;

/**
 * @Type Graph
 * @Desc
 * @author 52489
 * @date 2019年7月4日
 * @Version V1.0
 */
public class Graph {
    private Vertex[] vertexs;
    private int currentSize;
    public int[][] adjMat;
    public boolean visited;
    private Stack<Integer> stack = new Stack<>();
    // 当前遍历的下标
    private int currentIndex;

    /**
     * @param vertexs
     * @param currentSize
     * @param adjMat
     */
    public Graph(int size) {
        vertexs = new Vertex[size];
        adjMat = new int[size][size];
    }

    public void addVertex(Vertex v) {
        vertexs[currentSize++] = v;
    }

    public void addEdge(String v1, String v2) {
        int index1 = 0;
        for (int i = 0; i < vertexs.length; i++) {
            if (vertexs[i].getValue().equals(v1)) {
                index1 = i;
                break;

            }
        }

        int index2 = 0;
        for (int i = 0; i < vertexs.length; i++) {
            if (vertexs[i].getValue().equals(v2)) {
                index2 = i;
                break;
            }
        }

        adjMat[index1][index2] = 1;
        adjMat[index2][index1] = 1;

    }

    // 深度优先
    public void dfs() {
        // 把第0个顶点标记为已访问状态
        vertexs[0].visited = true;
        // 把第0个顶点下标
        stack.push(0);
        System.out.println(vertexs[0].getValue());
        // 遍历
        out: while (!stack.isEmpty()) {
            for (int i = currentIndex + 1; i < vertexs.length; i++) {
                // 如果和下个遍历的元素是通的
                if (adjMat[currentIndex][i] == 1 && vertexs[i].visited == false) {
                    stack.push(i);
                    vertexs[i].visited = true;
                    System.out.println(vertexs[i].getValue());
                    continue out;
                }
            }
            // 弹出栈顶元素
            stack.pop();
            // 修改当前位置为栈顶元素的位置
            if (!stack.isEmpty()) {
                currentIndex = stack.peek();
            }
        }
    }

}
